// https://leetcode.cn/problems/as-far-from-land-as-possible/description/

// 算法思路总结：
// 1. 多源BFS从所有陆地单元格开始同步扩展
// 2. 计算每个海洋到最近陆地的曼哈顿距离
// 3. 使用距离矩阵记录最短路径长度
// 4. 返回所有海洋单元格中的最大距离值
// 5. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

class Solution 
{
public:
    int n;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    typedef pair<int, int> PII;

    int maxDistance(vector<vector<int>>& grid)
    {
        n = grid.size();

        queue<PII> q;
        vector<vector<int>> dist(n, vector<int>(n, -1));

        for (int i = 0 ; i < n ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (grid[i][j] == 1)
                {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        if (q.size() == 0 || q.size() == n * n)
        {
            return -1;
        }

        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && y >= 0 && x < n && y < n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    q.push({x, y});
                }
            }
        }

        int ret = 0;
        for (int i = 0 ; i < n ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                ret = max(ret, dist[i][j]);
            }
        }

        return ret;
    }
};

int main()
{
    vector<vector<int>> grid1 = {{1,0,1},{0,0,0},{1,0,1}};
    vector<vector<int>> grid2 = {{1,0,0},{0,0,0},{0,0,0}};
    Solution sol;

    cout << sol.maxDistance(grid1) << endl;
    cout << sol.maxDistance(grid2) << endl;

    return 0;
}